package algotithm.weekendrace.leetcode239.test4;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author 25068
 * @Date 2021/5/2 10:28
 * @Title 5748. 包含每个查询的最小区间
 */
public class Solution {

    public static void main(String[] args) {
        int[][] intervals = {{1,4},{2,4},{3,6},{4,4}};
        int[] queries = {2,3,4,5};
        Solution solution = new Solution();
        int[] ans = solution.minInterval(intervals,queries);
        for (int i = 0; i < ans.length; i++) {
            System.out.print(ans[i] + " ");
        }
    }

    public int[] minInterval(int[][] intervals, int[] queries) {
        //对区间按起始位置升序排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        //将queries的值queries[i]和序号i封装到一个二维整数数组
        int n = queries.length;
        int[][] p = new int[n][2];
        for(int i = 0; i < n; i++){
            p[i][0] = queries[i];
            p[i][1] = i;
        }
        //将p按查询位置p[i][0]升序排序
        Arrays.sort(p, (v1,v2) -> v1[0] - v2[0]);
        int[] ans = new int[n];
        //将ans事先用-1填充
        Arrays.fill(ans, -1);
        //创建优先队列
        PriorityQueue<int[]> queue = new PriorityQueue<>((v1, v2) -> v1[1] - v1[0] - v2[1] +v2[0]);
        //未遍历到的intervals起始位置
        int index = 0;
        for(int i = 0; i < n; i++){
            //将所有起始位置小于等于查询位置的区间intervals[i]添加到优先队列中
            while(index < intervals.length && p[i][0] >= intervals[index][0]){
                queue.offer(new int[]{intervals[index][0], intervals[index][1]});
                index++;
            }
            //将队列中区间长度最短但区间结束位置小于查询位置的区间弹出队列
            while(!queue.isEmpty() && queue.peek()[1] < p[i][0]){
                queue.poll();
            }
            //如果队列不为空，则将最短区间的长度添加到对应的查询结果中ans[p[i][1]]
            if(!queue.isEmpty()){
                int[] temp = queue.peek();
                ans[p[i][1]] = temp[1] - temp[0] + 1;
            }
        }
        return ans;
    }
}
